package 算法.NiuKe.JZ;

import java.util.ArrayList;

/**
 * @author:谢君臣
 * @Date:2021/4/139:36
 * @version:1.0
 * @function:   小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。
 *               但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。
 *               没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,
 *               你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
 */
public class JZ41 {
    public static void main(String[] args) {
        FindContinuousSequence(3);
    }
    public static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        int i = 2;
        while (true){
            int n = sum/i;
            if (n-i/2<0||i>=sum) {
                break;
            }
            if (sum%i==0&&i%2==0){
                    i++;
            }else {
                int l = n-i/2,r = n+i/2;
                if (l == 0)l++;
                lists = addList(lists,i,l,r,sum);
                i++;
            }
        }
        return lists;
    }

    private static ArrayList<ArrayList<Integer>> addList(ArrayList<ArrayList<Integer>> lists, int i, int l, int r, int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        if (l==0)l++;
        int temp = l,count=0,size = r-l;
        for (int k = 0; k <= size ; k++) {
            list.add(temp);
            if (k>=i){count -=l++;list.remove(0);}
            count +=temp++;
            if (count==sum)lists.add(0,list);
        }
        return lists;
    }
}
